Data is communicated between computers over networks, such as the Internet. The data is typically communicated over the network as a series of packets using, for example, Internet Protocol. Typically, the packets are communicated from one computer to another using one or more routers. Each router is configured to receive packets and determine where to forward the packet. Often, this determination is made in a manner that delivers the packet to its destination with the fewest number of routers (or other devices) being involved.
In order for a router to determine where to forward a given packet, the router maintains information about what devices (e.g., computers, other routers, etc.) it is connected to on the network. In addition, the router may also include information about what each of the aforementioned devices is connected to on the network. Using this information, the router can determine the most efficient path to move the packet directly to or closer to its destination.
As the size of networks grow, the information maintained by a given router increases. As a result, the overhead required to maintain the information in the router also increases. For example, if the network topology in which a router is located changes (e.g., one of the devices to which the router is connected becomes unavailable), the router must take steps to update its information. Given the amount of information maintained by the router, the overhead required to keep the information in the router current may be significant.